package class5;

import common.TreeNode;
import common.TreeNodeUtils;

/**
 * https://leetcode.cn/problems/binary-tree-maximum-path-sum/
 * 求⼆叉树中最⼤路径和
 */
public class Code19_maxPathSum {
    public static void main(String[] args) {
        TreeNode treeNode = TreeNodeUtils.getMirrors();
        int maxPathSum = maxPathSum(treeNode);
        System.out.println(maxPathSum);

    }

    public static int maxPathSum(TreeNode treeNode) {
        process(treeNode);
        return maxSum;
    }

    // 最大路径和
    public static int maxSum = Integer.MIN_VALUE;

    public static int process(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        }
        // 递归计算左右子树的最大路径和，如果小于0则选择0
        int L_maxPath = Math.max(process(treeNode.left), 0); // 左子树的最大路径和
        int R_maxPath = Math.max(process(treeNode.right), 0); // 右子树的最大路径和

        // 当前节点的最大左右路径和
        int cur = L_maxPath + R_maxPath + treeNode.val;

        // 比较并更新全局最大路径和
        maxSum = Math.max(cur, maxSum);

        // 返回当前节点的最大路径和
        return treeNode.val + Math.max(L_maxPath, R_maxPath);
    }


}
